package com.dyz.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum15 {
    public static void main(String[] args) {
        int[] a = new int[]{-1,0,1,2,-1,-4};
        List<List<Integer>> li = new ThreeSum15().threeSum(a);
    }
    //排序 + 双指针
    //标签：数组遍历
    //首先对数组进行排序，排序后固定一个数nums[i],在使用左右指针指向nums[i]后面的两端，数字分别为nums[L]和nums[R],计算三个数的和sum， 判断是否马满足为0，满足添加进结果集
    //如果nums[i]大于0，则三个数之和必然无法等于0，结束循环
    //当sum==0时，nums[L]==nums[L+1]则会导致结果重复，应该跳过，L++
    //当sum==0时，nums[R]==nums[R-1] 则会导致结果重复，应该跳过，R--
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if(nums==null||nums.length==0||len<3){return ans;}
        Arrays.sort(nums);//排序
        for(int i=0; i<len; i++){
            if(nums[i]>0){ break;} // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if(i>0 && nums[i] == nums[i-1]){continue;}
            int L = i+1;
            int R = len-1;
            while (L<R){
                int sum = nums[i]+nums[L]+nums[R];
                if(sum==0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) {L++;} // 去重
                    while (L<R && nums[R] == nums[R-1]) {R--; }// 去重
                    L++;
                    R--;
                }else if (sum<0){L++;}
                else if (sum>0){R--;}
            }
        }
        return ans;


    }

}
